All You Need to Know About Graphs in Data Structures

Graphs in Data Structure

Graphs in data structure are a visual representation of relationships and connections between entities. They consist of nodes (vertices) and edges that connect these nodes. The relationships between nodes can be directional or bidirectional, forming the basis of various applications. Let us understand this with an example :

In this code we create a graph and create a traversal. The output shows the order in which nodes are visited during the traversal.

class Graph:

def __init__(self):

self.adjacency_list = {}

def add_node(self, node):

if node not in self.adjacency_list:

self.adjacency_list[node] = []

def add_edge(self, node1, node2):

# Assuming an undirected graph

self.adjacency_list[node1].append(node2)

self.adjacency_list[node2].append(node1)

def dfs(self, start_node, visited=None):

if visited is None:

visited = set()

print(start_node, end=" ")

visited.add(start_node)

for neighbor in self.adjacency_list[start_node]:

if neighbor not in visited:

self.dfs(neighbor, visited)

# Example usage:

graph = Graph()

# Adding nodes

graph.add_node(1)

graph.add_node(2)

graph.add_node(3)

graph.add_node(4)

# Adding edges

graph.add_edge(1, 2)

graph.add_edge(1, 3)

graph.add_edge(2, 4)

# Output: 1 2 4 3

print("DFS Traversal:")

graph.dfs(1)

Also Read:

• Learning Data Structures In Python, Types, and Techniques
• Understanding Data Structures Basics, Benefits and Project Ideas

Types of Graphs

There are several types of graphs in data structures. Given below are the various types of graphs that are used in data structure with examples:

1. Undirected Graphs

This is one of the important graphs types in data structure. In an undirected graph in data structure, the edges have no direction. The relationship between nodes is mutual, creating a symmetrical structure. Think of it as a two-way street where traffic can flow in both directions.

Example: Consider a social network where individuals are represented as nodes, and friendships are the undirected edges connecting them.

2. Directed Graphs (Digraphs)

In a directed graph, edges have a direction, indicating a one-way relationship between nodes. It is like a network of one-way streets, where the flow of information or influence is specific.

Example: In a network of web pages, directed edges could represent hyperlinks, guiding users from one page to another.

3. Weighted Graphs

Weighted graphs assign a numerical value (weight) to each edge. This weight often represents a cost, distance, or some other metric, adding an extra layer of information to the relationships.

Example: This graph data structure example shows a transportation network, with nodes as cities and weighted edges representing travel distances, showcasing the utility of weighted graphs.

4. Cyclic Graphs

Cyclic graphs exhibit cycles, indicating the presence of closed loops or circuits within their structure. Navigating through the nodes can lead you back to your starting point.

5. Acyclic Graphs

In contrast, acyclic graphs have no cycles. They form a tree-like structure, with nodes connected in a way that prevents the creation of closed loops.

What is a Graph Data Structure?

A graph data structure is a systematic way of organising and storing graph information in computer memory. It involves defining the nodes and edges, along with any additional properties like weights. This structured representation allows for efficient manipulation and traversal of graphs in algorithms and applications.

Also Read: Top 50 Data Structures And Algorithms Interview Questions

Graph Traversal in Data Structure

Graph traversal is the process of systematically visiting all the nodes in a graph. There are two primary methods:

Depth-First Search (DFS):

DFS explores as far as possible along each branch before backtracking. It is akin to wandering through a maze, exploring one path fully before considering alternatives.

Breadth-First Search (BFS):

BFS explores a graph level by level, starting from the source node. It is like ripples in a pond, moving outward in concentric circles.

These traversal methods are fundamental in understanding the structure and relationships within a graph.

Explore Computer Science Certification Courses by Top Providers

• Edx Computer Science Courses & Certifications
• Swayam Computer Science Courses & Certifications
• Coursera Computer Science Courses & Certifications
• Udemy Computer Science Courses & Certifications
• Udacity Computer Science Courses & Certifications
• Simplilearn Computer Science Courses & Certifications
• Futurelearn Computer Science Courses & Certifications
• Upskillist Computer Science Courses & Certifications

Conclusion

Graphs in data structure are not just a theoretical concept; they are a practical and powerful tool for solving real-world problems. Whether representing social connections, web structures, or transportation networks, graphs offer a visual and intuitive way to model relationships. Understanding types of graphs and their methodologies equips you with the skills to navigate and analyse these complex structures.